package com.breeze.heap;

/**
 * 包含最大最小堆化、构建堆、堆常用操作、堆排序以及堆建立的优先级队列
 */
// TODO:堆常用操作、堆排序以及堆建立的优先级队列
public class Heap<T extends Comparable> {
    /**
     * 构建最大或最小堆
     *
     * @param a
     * @param heapSize
     * @param maxHeap
     */
    public void buildHeap(T[] a, int heapSize, boolean maxHeap) {
        for (int i = heapSize - 1; i >= 0; i--) {
            if (maxHeap) {
                heapify(a, i, heapSize);
            } else {
                minHeapify(a, i, heapSize);
            }
        }
    }

    /**
     * 最大堆化
     *
     * @param a        表示堆的数组
     * @param i        需要被堆化的下标
     * @param heapSize 数组中表示表示堆的长度
     */
    public void heapify(T[] a, int i, int heapSize) {
        int l = left(i);
        int r = right(i);
        int largest = -1;
        if (l < heapSize && a[i].compareTo(a[l]) < 0) {
            largest = l;
        } else {
            largest = i;
        }
        if (r < heapSize && a[largest].compareTo(a[r]) < 0) {
            largest = r;
        }
        if (i != largest) {
            T temp = a[i];
            a[i] = a[largest];
            a[largest] = temp;
            heapify(a, largest, heapSize);
        }
    }

    /**
     * 最小堆化
     * 时间复杂度：O(log n)
     * 空间复杂度：O(1)
     *
     * @param a
     * @param i
     * @param heapSize
     */
    public void minHeapify(T[] a, int i, int heapSize) {
        int l = left(i);
        int r = right(i);
        int smallest = i;
        if (l < heapSize && a[i].compareTo(a[l]) > 0) {
            smallest = l;
        }
        if (r < heapSize && a[smallest].compareTo(a[r]) > 0) {
            smallest = r;
        }

        if (smallest != i) {
            // change
            T temp = a[i];
            a[i] = a[smallest];
            a[smallest] = temp;
            minHeapify(a, smallest, heapSize);
        }
    }

    /**
     * 根据排序规则进行堆排序
     * 时间复杂度：O(nlog n)
     * 空间复杂度：O(1)
     */
    public void sort(T[] a, boolean asc) {
        // 升序排列，构建最大堆;降序排列构建最小堆
        buildHeap(a, a.length, asc);
        for (int i = a.length - 1; i > 0; i--) {
            swap(a, 0, i);
            buildHeap(a, i, asc);
        }
    }

    /**
     * 返回左孩子下标
     */
    public int left(int i) {
        return (i + 1) * 2 - 1;
    }

    /**
     * 返回右孩子下标
     */
    public int right(int i) {
        return (i + 1) * 2;
    }

    /**
     * 返回父亲下标
     */
    public int parent(int i) {
        // i为根结点
        if (i == 0) {
            return -1;
        }
        return (i - 1) / 2;
    }

    public static <T> void swap(T[] arr, int i1, int i2) {
        T temp = arr[i1];
        arr[i1] = arr[i2];
        arr[i2] = temp;
    }

    public static void main(String[] args) {
        Heap<Integer> integerHeap = new Heap<>();
        // 最大堆化测试
        Integer[] nums = {10, 2, 9, 6, 4, 5, 8, 1, 3};
        integerHeap.heapify(nums, 1, nums.length);
        for (Integer num : nums) {
            System.out.print(num + ",");// 10,6,9,3,4,5,8,1,2
        }
        System.out.println();
        // 最小堆化测试
        Integer[] nums1 = {1, 2, 3, 8, 5, 9, 10, 7, 6};
        integerHeap.minHeapify(nums1, 3, nums1.length);
        for (Integer num : nums1) {
            System.out.print(num + ",");// 1,2,3,6,5,9,10,7,8
        }
        System.out.println();
        // 构建最大堆测试
        Integer[] nums2 = {7, 3, 6, 5, 8, 9, 2, 1, 4};
        integerHeap.buildHeap(nums2, nums2.length, true);
        for (Integer num : nums2) {
            System.out.print(num + ",");// 9,8,7,5,3,6,2,1,4
        }
        System.out.println();
        // 构建最小堆测试
        Integer[] nums3 = {7, 3, 6, 5, 8, 9, 2, 1, 4};
        integerHeap.buildHeap(nums3, nums3.length, false);
        for (Integer num : nums3) {
            System.out.print(num + ",");// 1,3,2,4,8,9,6,5,7
        }
        System.out.println();
        // 堆排序测试
        Integer[] nums4 = {7, 3, 6, 5, 8, 9, 2, 1, 4};
        integerHeap.sort(nums4, true);
        for (Integer num : nums4) {
            System.out.print(num + ",");// 1,2,3,4,5,6,7,8,9
        }
        System.out.println();
        integerHeap.sort(nums4, false);
        for (Integer num : nums4) {
            System.out.print(num + ",");// 9,8,7,6,5,4,3,2,1
        }

    }

}
